"""
143. 重排链表
中等
相关标签
premium lock icon
相关企业
给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。



示例 1：



输入：head = [1,2,3,4]
输出：[1,4,2,3]
示例 2：



输入：head = [1,2,3,4,5]
输出：[1,5,2,4,3]


提示：

链表的长度范围为 [1, 5 * 104]
1 <= node.val <= 1000
"""
from typing import Optional, List


# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        list:List[Optional[ListNode]] = []
        cur = head
        while cur:
            list.append(cur)
            cur = cur.next
        #组成目标的顺序
        targetList:List[Optional[ListNode]] = []
        isLeft = True
        while list:
            if isLeft:
                targetList.append(list.pop(0))
            else:
                targetList.append(list.pop())
            isLeft = not isLeft
        for i in range(len(targetList)):
            if i == len(targetList)-1:
                #最后一位指向空
                targetList[i].next = None
            else:
                targetList[i].next = targetList[i+1]
        return head
if __name__ == '__main__':
    def print_list(head: Optional[ListNode]) -> None:
        """打印链表所有节点的值"""
        current = head
        values = []
        while current:
            values.append(current.val)
            current = current.next
        print(" -> ".join(map(str, values)))


    # 或者更简洁的版本
    def print_linked_list(head: Optional[ListNode]) -> None:
        """循环打印链表节点"""
        while head:
            print(head.val, end=" -> " if head.next else "\n")
            head = head.next

    s = Solution()
    # 测试用例 1
    # 输入：head = [1,2,3,4]
    node1 = ListNode(1)
    node2 = ListNode(2)
    node3 = ListNode(3)
    node4 = ListNode(4)
    node1.next = node2
    node2.next = node3
    node3.next = node4
    # 预期输出：[1,4,2,3]
    print("重排前:")
    print_list(node1)

    s.reorderList(node1)

    print("重排后:")
    print_list(node1)  # 输出: 1 -> 4 -> 2 -> 3

    # 测试用例 2
    # 输入：head = [1,2,3,4,5]
    node1 = ListNode(1)
    node2 = ListNode(2)
    node3 = ListNode(3)
    node4 = ListNode(4)
    node5 = ListNode(5)
    node1.next = node2
    node2.next = node3
    node3.next = node4
    node4.next = node5
    # 预期输出：[1,5,2,4,3]
    print("重排前:")
    print_list(node1)

    s.reorderList(node1)

    print("重排后:")
    print_list(node1)  # 输出: 1 -> 4 -> 2 -> 3